#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
typedef char STDatatype;

typedef struct StackType
{
	STDatatype* data;
	int top;
	int capacity;
}ST;

void initstack(ST** stack)
{
	assert(stack);
	*stack = (ST*)malloc(sizeof(ST));
	(*stack)->data = NULL;
	(*stack)->top = 0;
	(*stack)->capacity = 0;
}

void stackPush(ST* stack, STDatatype ch)
{
	assert(stack);
	if (stack->top == stack->capacity)
	{
		int newcapacity = stack->capacity == 0 ? 4 : 2 * stack->capacity;
		stack->data = (STDatatype*)realloc(stack->data, newcapacity * sizeof(STDatatype));
		if (stack->data == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		stack->capacity = newcapacity;
	}
	stack->data[stack->top] = ch;
	stack->top++;
}

void stackDestory(ST** stack)
{
	(*stack)->top = 0;
	(*stack)->capacity = 0;
	free(*stack);
	*stack = NULL;
}

int stacktop(ST* stack)
{
	assert(stack);

	return stack->top - 1;
}

void stackPop(ST* stack)
{
	assert(stack);
	assert(stack->top > 0);
	stack->top--;
}

//bool isValid(char* s) 
//{
//	ST* stack;
//	initstack(&stack);
//	int i = 0, j = 0, pos = 0;
//	j = strlen(s);
//	while (i < j)
//	{
//		switch (s[i])
//		{
//		case '{':
//			stackPush(stack, s[i]);
//			i++;
//			break;
//		case '[':
//			stackPush(stack, s[i]);
//			i++;
//			break;
//		case '(':
//			stackPush(stack, s[i]);
//			i++;
//			break;
//		case '}':
//			pos = stacktop(stack);
//			if ('{' == stack->data[pos])
//			{
//				stackPop(stack);
//				i++;
//			}
//			else
//			{
//				return false;
//			}
//			break;
//		case ']':
//			pos = stacktop(stack);
//			if ('[' == stack->data[pos])
//			{
//				stackPop(stack);
//				i++;
//			}
//			else
//			{
//				return false;
//			}
//			break;
//		case ')':
//			pos = stacktop(stack);
//			if ('(' == stack->data[pos])
//			{
//				stackPop(stack);
//				i++;
//			}
//			else
//			{
//				return false;
//			}
//			break;
//		}
//	}
//	if (stack->top == 0)
//	{
//		return true;
//	}
//	else
//	{
//		return false;
//	}
//	free(stack->data);
//	stack->capacity = 0;
//	stack->top = 0;
//}

int stackempty(ST* stack)
{
	assert(stack);
	if (stack->top > 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
//switch...case...
/*bool isValid(char* s)
{
	ST* stack;
	initstack(&stack);
	int i = 0, j = 0, pos = 0;
	j = strlen(s);
	while (i < j)
	{
		switch (s[i])
		{
		case '{':
			stackPush(stack, s[i]);
			i++;
			break;
		case '[':
			stackPush(stack, s[i]);
			i++;
			break;
		case '(':
			stackPush(stack, s[i]);
			i++;
			break;
		case '}':
			if (stackempty(stack))
			{
				pos = stacktop(stack);
				if ('{' == stack->data[pos])
				{
					stackPop(stack);
					i++;
				}
				else
				{
					return false;
				}
				break;
			}
			return false;
		case ']':
			if (stackempty(stack))
			{
				pos = stacktop(stack);
				if ('[' == stack->data[pos])
				{
					stackPop(stack);
					i++;
				}
				else
				{
					return false;
				}
				break;
			}
			return false;
		case ')':
			if (stackempty(stack))
			{
				pos = stacktop(stack);
				if ('(' == stack->data[pos])
				{
					stackPop(stack);
					i++;
				}
				else
				{
					return false;
				}
				break;
			}
			return false;
		}
	}
	if (stack->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}*/

//if...else...
bool isValid(char* s)
{
	ST* stack;
	initstack(&stack);
	int i = 0;
	int j = strlen(s);
	while (i < j)
	{
		if (s[i] == '(' || s[i] == '[' || s[i] == '{')
		{
			stackPush(stack, s[i]);
			i++;
		}
		else
		{
			if (stackempty(stack))
			{
				int pos = stacktop(stack);
				if ((stack->data[pos] == '(' && s[i] == ')') || (stack->data[pos] == '[' && s[i] == ']') || (stack->data[pos] == '{' && s[i] == '}'))
				{
					stackPop(stack);
					i++;
				}
				else
				{
					return false;
				}
			}
			else
			{
				return false;
			}
		}
	}
	if (stack->top == 0)
	{
		return true;
	}
	return false;
}

int main()
{
	char* str = "()";
	if (isValid(str))
	{
		printf("true");
	}
	else
	{
		printf("false");
	}

	return 0;
}